package it.storm.solution;

import java.util.ArrayList;
import java.util.List;

/**
 * 1560. 圆形赛道上经过次数最多的扇区
 * https://leetcode-cn.com/problems/most-visited-sector-in-a-circular-track/
 */
public class Solutions_1560 {
    public static void main(String[] args) {
//        int n = 4;
//        int[] rounds = {1, 3, 1, 2};  // output: {1, 2}

//        int n = 2;
//        int[] rounds = {2, 1, 2, 1, 2, 1, 2, 1, 2};  // output: {2}

        int n = 7;
        int[] rounds = {1, 3, 5, 7};  // output: {1, 2, 3, 4, 5, 6, 7}

        List<Integer> result = mostVisited(n, rounds);
        System.out.println(result);
    }

    /**
     * 由于马拉松全程只会按照同一个方向跑，中间不论跑了多少圈，对所有扇区的经过次数的贡献都是相同的。
     * 因此此题的答案仅与起点和终点相关。
     * 关键：从起点沿着逆时针方向走到终点的这部分扇区，就是 经过次数最多的 扇区。
     * 起点即是 rounds 的第一个元素，终点即是 rounds 中的最后一个元素
     */
    public static List<Integer> mostVisited(int n, int[] rounds) {
        List<Integer> res = new ArrayList<>();
        int start = rounds[0], end = rounds[rounds.length - 1];
        // 保证存储的结果按照扇区编号 升序 排列
        if (start <= end) {
            // start = 1, end = 2 的情况
            for (int i = start; i <= end; i++) {
                res.add(i);
            }
        } else {
            // start = 3, end = 1 的情况，分两个 for 循环，存储扇区编号
            for (int i = 1; i <= end; i++) {
                // [1, end] 区间
                res.add(i);
            }
            for (int i = start; i <= n; i++) {
                // [start, n] 区间
                res.add(i);
            }
        }
        return res;
    }
}
